package day_2022_9_to_12.Day;

import java.util.Stack;

/**
 * @author haomin
 * @date 2022/10/04 16:22
 **/
public class Day33_1_Num921_MinAddToMakeValid {
    class Solution {
        public int minAddToMakeValid(String s) {
            while(s.contains("()")){
                s = s.replace("()", "");
            }
            return s.length();
        }
    }
    // 方法二：找规律
// 出现一个'('个数+1；
// 若已出现'('，再出现一个右')'个数-1，否则个数加+1
    class Solution2 {
        public int minAddToMakeValid(String s) {
            int l = 0, r = 0;
            for(char c : s.toCharArray()){
                if(c == '(') l++;
                else {
                    if(l > 0) l--;
                    else r++;
                }
            }
            return l + r;
        }
    }
    class Solution3 {
        public int minAddToMakeValid(String s) {
            Stack<Character> stack = new Stack<>();
            if(s.length() == 0) return 0;
            int i = 0;
            int count = 0;
            stack.push(s.charAt(i));
            while (i < s.length()-1){
                i++;
                char a = stack.peek();
                char b = s.charAt(i);
                if(a == '(' && b == ')'){
                    stack.pop();
                    i++;
                    if(i < s.length() && stack.isEmpty()){
                        stack.push(s.charAt(i));
                    }else if(i < s.length() && !stack.isEmpty()){
                        i--;
                        continue;
                    }else if(i >= s.length()) break;
                }else if(a == '(' && b == '('){
                    stack.push(b);
                }else if(a == ')'){
                    stack.pop();
                    count++;
                    stack.push(b);
                }
            }
            count = count + stack.size();
            return count;
        }
    }
}